/*
 * Copyright (c) 2023. Shanghai HEADING information Engineering Co., Ltd. All rights reserved.
 */

package com.lovely602.algorithm.combination;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合算法
 *
 * @author lizhixing
 */
public class Combination {

  public static void main(String[] args) {
    char[] sources = { 'A', 'B', 'C', 'D' };
    List<List<Character>> result = new ArrayList<>();
    combination(sources, sources.length, 3, null, result);
    System.out.print("构成的组合数据：");
    System.out.print(result);
    System.out.println();
    System.out.print("构成的排列数据：");
    System.out.print(permutation(sources, sources.length, 3));
  }

  /**
   * 求出源数组中的组合
   *
   * @param sources
   *     源数组
   * @param length
   *     源数组的长度
   * @param number
   *     目标数组的长度
   * @param target
   *     中间数据
   * @param targets
   *     目标数据
   */
  public static void combination(char[] sources, int length, int number, List<Character> target,
      List<List<Character>> targets) {
    assert sources != null;
    assert targets != null;
    if (target == null) {
      target = new ArrayList<>();
    }
    if (number == 0) {
      List<Character> temp = new ArrayList<>(target);
      targets.add(temp);
    } else {
      for (int i = sources.length - length; i <= sources.length - number; i++) {
        target.add(sources[i]);
        combination(sources, sources.length - i - 1, number - 1, target, targets);
        target.remove(target.size() - 1);
      }
    }
  }

  /**
   * 求出源数组中的排列
   *
   * @param sources
   *     源数组
   * @param length
   *     源数组的长度
   * @param number
   *     目标数组的长度
   * @return 目标排列组合
   */
  public static List<List<Character>> permutation(char[] sources, int length, int number) {
    assert sources != null;
    List<List<Character>> temp = new ArrayList<>();
    List<Character> target = new ArrayList<>();
    combination(sources, length, number, target, temp);

    List<List<Character>> result = new ArrayList<>();
    for (int i = 0; i < temp.size(); i++) {
      char[] tc = new char[temp.get(i).size()];
      for (int j = 0; j < tc.length; j++) {
        tc[j] = temp.get(i).get(j);
      }
      result.addAll(permutation(tc, tc.length));
    }
    return result;
  }

  private static List<List<Character>> permutation(char[] sources, int length) {
    assert sources != null;
    if (length == 1) {
      List<Character> target = new ArrayList<>();
      List<List<Character>> temp = new ArrayList<>();
      target.add(sources[0]);
      temp.add(target);
      return temp;
    } else {
      List<List<Character>> temp = permutation(sources, length - 1);
      List<List<Character>> result = new ArrayList<>();
      for (int i = 0; i < temp.size(); i++) {
        for (int j = 0; j < length; j++) {
          List<Character> target = new ArrayList<>(temp.get(i));
          if (j < length - 1) {
            target.add(j, sources[length - 1]);
            result.add(target);
          } else {
            target.add(sources[length - 1]);
            result.add(target);
          }
        }
      }
      return result;
    }
  }

}
